// Src: https://github.com/ubilabs/kd-tree-javascript/blob/master/src/web/kdTree.js
function KDTree(objectList, distanceFunction, dimensionAttributes) {"use strict";
	this.distanceFunction = distanceFunction;
	this.dimensionAttributes = dimensionAttributes;
	this.root = this.buildTree(objectList, 0, null);
}

KDTree.prototype.buildTree = function(objectList, depth, parent) {"use strict";
	var dimensionNo, auxDimensionAttributes, median, newNode, left, right;
	//
	if (!objectList || objectList.length === 0) {
		return null;
	}
	//
	dimensionNo = depth % this.dimensionAttributes.length;
	//
	if (objectList.length === 1) {
		return new KDTree_Node(objectList[0], dimensionNo, parent);
	}
	//
	// Sort list of points by single dimension
	auxDimensionAttributes = this.dimensionAttributes;
	objectList.sort(function(obj1, obj2) {
		return obj1[auxDimensionAttributes[dimensionNo]] - obj2[auxDimensionAttributes[dimensionNo]];
	});
	//
	median = Math.floor(objectList.length / 2);
	newNode = new KDTree_Node(objectList[median], dimensionNo, parent);
	left = this.buildTree(objectList.slice(0, median), depth + 1, newNode);
	right = this.buildTree(objectList.slice(median + 1), depth + 1, newNode);
	newNode.left = left;
	newNode.right = right;
	return newNode;
};

KDTree.prototype.toString = function() {"use strict";
	return "(KDTree " + this.root + ")";
};

KDTree.prototype.findNearest = function(point, maxNodes, maxDistance) {"use strict";
	var scoreFunction, i, result, bestNodes;
	//
	// Score function maximizes -binaryHeapNode[1], that is, minimizes binaryHeamNode.distance
	scoreFunction = function(binaryHeapNode) {
		return -binaryHeapNode[1];
	};
	//
	// Create binary heap of 2 positions array [object, distance]
	// binary heap is sorted by 2nd position of the array (distance).
	bestNodes = new BinaryHeap(scoreFunction);
	//
	// Fills with maxNodes empty nodes
	if (maxDistance) {
		for ( i = 0; i < maxNodes; i = i + 1) {
			bestNodes.push([null, maxDistance]);
		}
	}
	//
	// Looks for nodes
	this.findNearest_nearestSearch(point, this.root, maxNodes, this.distanceFunction, this.dimensionAttributes, bestNodes);
	//
	// Fills results array with all non null values in the result (null values -in case they exist- are at maxDistance)
	result = [];
	for ( i = maxNodes - 1; i >= 0; i = i - 1) {
		if (bestNodes.content[i][0]) {
			result.push([bestNodes.content[i][0].obj, bestNodes.content[i][1]]);
		}
	}
	return result;
};

KDTree.prototype.findNearest_nearestSearch = function(point, kdtreeNode, maxNodes, distanceFunction, dimensionAttributes, bestNodes) {"use strict";
	var bestChild, dimensionAttribute, ownDistance, linearPoint, i, linearDistance, otherChild;
	//
	//Distance from current kdtreeNode object to the point
	ownDistance = distanceFunction(point, kdtreeNode.obj);
	//
	//
	//If distance < worst distance in the list of best nodes
	if (ownDistance < bestNodes.peek()[1]) {
		//Add node and remove first element (farthest)
		bestNodes.push([kdtreeNode, ownDistance]);
		bestNodes.pop();
	}
	//
	//If the node has no left or right sub-trees, add node to the list of best nodes.
	if (kdtreeNode.right === null && kdtreeNode.left === null) {
		return;
	}
	//
	// Tries first in the subtree closest to the point (not always the best choice)
	dimensionAttribute = dimensionAttributes[kdtreeNode.dimensionNo];
	if (kdtreeNode.right === null) {
		bestChild = kdtreeNode.left;
	} else if (kdtreeNode.left === null) {
		bestChild = kdtreeNode.right;
	} else {
		if (point[dimensionAttribute] < kdtreeNode.obj[dimensionAttribute]) {
			bestChild = kdtreeNode.left;
		} else {
			bestChild = kdtreeNode.right;
		}
	}
	this.findNearest_nearestSearch(point, bestChild, maxNodes, distanceFunction, dimensionAttributes, bestNodes);
	//
	// Tries then in the other subtree, if the distance to the other side of the partition is lower than the worst distance found so far.
	// Makes up point in the border and computes distance.
	linearPoint = {};
	for ( i = 0; i < dimensionAttributes.length; i = i + 1) {
		if (i === kdtreeNode.dimensionNo) {
			linearPoint[dimensionAttributes[i]] = point[dimensionAttributes[i]];
		} else {
			linearPoint[dimensionAttributes[i]] = kdtreeNode.obj[dimensionAttributes[i]];
		}
	}
	linearDistance = distanceFunction(linearPoint, kdtreeNode.obj);
	//
	// If there is any chance, tries with the nodes in the other sub-tree.
	if (linearDistance < bestNodes.peek()[1]) {
		otherChild = null;
		if (bestChild === kdtreeNode.left) {
			otherChild = kdtreeNode.right;
		} else {
			otherChild = kdtreeNode.left;
		}
		if (otherChild !== null) {
			this.findNearest_nearestSearch(point, otherChild, maxNodes, distanceFunction, dimensionAttributes, bestNodes);
		}
	}
};

KDTree.prototype.balanceFactor = function() {"use strict";
	function height(kdtreeNode) {
		if (kdtreeNode === null) {
			return 0;
		}
		return Math.max(height(kdtreeNode.left), height(kdtreeNode.right)) + 1;
	}

	function count(kdtreeNode) {
		if (kdtreeNode === null) {
			return 0;
		}
		return count(kdtreeNode.left) + count(kdtreeNode.right) + 1;
	}

	return height(this.root) / (Math.log(count(this.root)) / Math.log(2));
};

//Adds a new object to the tree
KDTree.prototype.insert = function(object) {"use strict";

	function innerSearch(kdtree, kdtreeNode, parent) {
		var dimensionAttribute;
		if (kdtreeNode === null) {
			return parent;
		}
		dimensionAttribute = kdtree.dimensionAttributes[kdtreeNode.dimensionNo];
		if (object[dimensionAttribute] < kdtreeNode.obj[dimensionAttribute]) {
			return innerSearch(kdtree, kdtreeNode.left, kdtreeNode);
		}
		return innerSearch(kdtree, kdtreeNode.right, kdtreeNode);
	}

	var insertPosition, newNode, dimensionAttribute;
	//Finds parent for the new node
	insertPosition = innerSearch(this, this.root, null);
	//
	//No parent found, it is the root node
	if (insertPosition === null) {
		this.root = new KDTree_Node(object, 0, null);
		return;
	}
	//
	//No parent found, it is the root node
	newNode = new KDTree_Node(object, (insertPosition.dimensionNo + 1) % this.dimensionAttributes.length, insertPosition);
	dimensionAttribute = this.dimensionAttributes[insertPosition.dimensionNo];
	if (object[dimensionAttribute] < insertPosition.obj[dimensionAttribute]) {
		insertPosition.left = newNode;
	} else {
		insertPosition.right = newNode;
	}
};

//Removes node
KDTree.prototype.remove = function(object) {"use strict";
	function nodeSearch(object, kdtreeNode, dimensionAttributes) {
		if (kdtreeNode === null) {
			return null;
		}
		if (kdtreeNode.obj === object) {
			return kdtreeNode;
		}
		var dimensionAttribute = dimensionAttributes[kdtreeNode.dimensionNo];
		if (object[dimensionAttribute] < kdtreeNode.obj[dimensionAttribute]) {
			return nodeSearch(object, kdtreeNode.left, dimensionAttributes);
		}
		return nodeSearch(object, kdtreeNode.right, dimensionAttributes);
	}
	//
	function findMax(kdtree, kdtreeNode, dimensionNo) {
		var dimensionAttribute, own, left, right, max;
		if (kdtreeNode === null) {
			return null;
		}
		dimensionAttribute = kdtree.dimensionAttributes[dimensionNo];
		if (kdtreeNode.dimensionNo === dimensionNo) {
			if (kdtreeNode.right !== null) {
				return findMax(kdtree, kdtreeNode.right, dimensionNo);
			}
			return kdtreeNode;
		}
		own = kdtreeNode.obj[dimensionAttribute];
		left = findMax(kdtree, kdtreeNode.left, dimensionNo);
		right = findMax(kdtree, kdtreeNode.right, dimensionNo);
		max = kdtreeNode;
		if (left !== null && left.obj[dimensionAttribute] > own) {
			max = left;
		}
		if (right !== null && right.obj[dimensionAttribute] > max.obj[dimensionAttribute]) {
			max = right;
		}
		return max;
	}
	//
	function findMin(kdtree, kdtreeNode, dimensionNo) {
		var dimensionAttribute, own, left, right, min;
		if (kdtreeNode === null) {
			return null;
		}
		dimensionAttribute = kdtree.dimensionAttributes[dimensionNo];
		if (kdtreeNode.dimensionNo === dimensionNo) {
			if (kdtreeNode.left !== null) {
				return findMin(kdtree, kdtreeNode.left, dimensionNo);
			}
			return kdtreeNode;
		}
		own = kdtreeNode.obj[dimensionAttribute];
		left = findMin(kdtree, kdtreeNode.left, dimensionNo);
		right = findMin(kdtree, kdtreeNode.right, dimensionNo);
		min = kdtreeNode;
		if (left !== null && left.obj[dimensionAttribute] < own) {
			min = left;
		}
		if (right !== null && right.obj[dimensionAttribute] < min.obj[dimensionAttribute]) {
			min = right;
		}
		return min;
	}
	//
	function removeNode(kdtree, kdtreeNode) {
		var pDimension, nextNode, nextObj;
		if (kdtreeNode.left === null && kdtreeNode.right === null) {
			if (kdtreeNode.parent === null) {
				kdtree.root = null;
				return;
			}
			pDimension = kdtree.dimensionAttributes[kdtreeNode.parent.dimensionNo];
			if (kdtreeNode.obj[pDimension] < kdtreeNode.parent.obj[pDimension]) {
				kdtreeNode.parent.left = null;
			} else {
				kdtreeNode.parent.right = null;
			}
			return;
		}
		if (kdtreeNode.left !== null) {
			nextNode = findMax(kdtree, kdtreeNode.left, kdtreeNode.dimensionNo);
		} else {
			nextNode = findMin(kdtree, kdtreeNode.right, kdtreeNode.dimensionNo);
		}
		nextObj = nextNode.obj;
		removeNode(kdtree, nextNode);
		kdtreeNode.obj = nextObj;
	}
	//
	var kdtreeNode = nodeSearch(object, this.root, this.dimensionAttributes);
	if (kdtreeNode === null) {
		return;
	}
	removeNode(this, kdtreeNode);
};

KDTree.prototype.updateNodeCoordinates = function(obj, point) {"use strict";
	//
	// Remove old object
	this.remove(obj);
	//
	// Update object coordinates
	var i;
	for (i = 0; i < this.dimensionAttributes.length; i = i + 1) {
		obj[this.dimensionAttributes[i]] = point[this.dimensionAttributes[i]];
	}
	//
	// Add updated object
	this.insert(obj);
}
